home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / lang / lisp / guile-ii.src / guile-ii / guile-src / libguile / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-06-13  |  4.9 KB  |  190 lines
  1. /*    Copyright (C) 1995 Free Software Foundation, Inc.
  2.  * 
  3.  * This program is free software; you can redistribute it and/or modify
  4.  * it under the terms of the GNU General Public License as published by
  5.  * the Free Software Foundation; either version 2, or (at your option)
  6.  * any later version.
  7.  * 
  8.  * This program is distributed in the hope that it will be useful,
  9.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.  * GNU General Public License for more details.
  12.  * 
  13.  * You should have received a copy of the GNU General Public License
  14.  * along with this software; see the file COPYING.  If not, write to
  15.  * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16.  *
  17.  * As a special exception, the Free Software Foundation gives permission
  18.  * for additional uses of the text contained in its release of GUILE.
  19.  *
  20.  * The exception is that, if you link the GUILE library with other files
  21.  * to produce an executable, this does not by itself cause the
  22.  * resulting executable to be covered by the GNU General Public License.
  23.  * Your use of that executable is in no way restricted on account of
  24.  * linking the GUILE library code into it.
  25.  *
  26.  * This exception does not however invalidate any other reasons why
  27.  * the executable file might be covered by the GNU General Public License.
  28.  *
  29.  * This exception applies only to the code released by the
  30.  * Free Software Foundation under the name GUILE.  If you copy
  31.  * code from other Free Software Foundation releases into a copy of
  32.  * GUILE, as the General Public License permits, the exception does
  33.  * not apply to the code that you add in this way.  To avoid misleading
  34.  * anyone as to the status of such modified files, you must delete
  35.  * this exception notice from them.
  36.  *
  37.  * If you write modifications of your own for GUILE, it is your choice
  38.  * whether to permit this exception to apply to your modifications.
  39.  * If you do not wish that, delete this exception notice.  
  40.  */
  41.  
  42.  
  43. #include <stdio.h>
  44. #include "_scm.h"
  45.  
  46.  
  47.  
  48. #ifndef floor
  49. extern double floor();
  50. #endif
  51.  
  52. #ifdef __STDC__
  53. unsigned long
  54. scm_hasher(SCM obj, unsigned long n, sizet d)
  55. #else
  56. unsigned long
  57. scm_hasher(obj, n, d)
  58.      SCM obj;
  59.      unsigned long n;
  60.      sizet d;
  61. #endif
  62. {
  63.   switch (7 & (int) obj) {
  64.   case 2: case 6:        /* INUMP(obj) */
  65.     return INUM(obj) % n;
  66.   case 4:
  67.     if ICHRP(obj)
  68.       return (unsigned)(scm_downcase[ICHR(obj)]) % n;
  69.     switch ((int) obj) {
  70. #ifndef SICP
  71.     case (int) EOL: d = 256; break;
  72. #endif
  73.     case (int) BOOL_T: d = 257; break;
  74.     case (int) BOOL_F: d = 258; break;
  75.     case (int) EOF_VAL: d = 259; break;
  76.     default: d = 263;        /* perhaps should be error */
  77.     }
  78.     return d % n;
  79.   default: return 263 % n;    /* perhaps should be error */
  80.   case 0:
  81.     switch TYP7(obj) {
  82.     default: return 263 % n;
  83.     case tc7_smob:
  84.       switch TYP16(obj) {
  85.       case tcs_bignums:
  86.       bighash: return INUM(scm_modulo(obj, MAKINUM(n)));
  87.       default: return 263 % n;
  88. #ifdef FLOATS
  89.       case tc16_flo:
  90.     if REALP(obj) {
  91.       double r = REALPART(obj);
  92.       if (floor(r)==r) {
  93.         obj = scm_inexact_to_exact (obj);
  94.         if IMP(obj) return INUM(obj) % n;
  95.         goto bighash;
  96.       }
  97.     }
  98.     obj = scm_number_to_string(obj, MAKINUM(10));
  99. #endif
  100.       }
  101.     case tcs_symbols: case tc7_string:
  102.       return scm_strhash(UCHARS(obj), (sizet) LENGTH(obj), n);
  103.     case tc7_vector: {
  104.       sizet len = LENGTH(obj);
  105.       SCM *data = VELTS(obj);
  106.       if (len>5) {
  107.     sizet i = d/2;
  108.     unsigned long h = 1;
  109.     while (i--) h = ((h<<8) + (scm_hasher(data[h % len], n, 2))) % n;
  110.     return h;
  111.       }
  112.       else {
  113.     sizet i = len;
  114.     unsigned long h = (n)-1;
  115.     while (i--) h = ((h<<8) + (scm_hasher(data[i], n, d/len))) % n;
  116.     return h;
  117.       }
  118.     }
  119.     case tcs_cons_imcar: case tcs_cons_nimcar:
  120.       if (d) return (scm_hasher(CAR(obj), n, d/2)+scm_hasher(CDR(obj), n, d/2)) % n;
  121.       else return 1;
  122.     case tc7_port:
  123.       return ((RDNG & CAR(obj)) ? 260 : 261) % n;
  124.     case tcs_closures: case tc7_contin: case tcs_subrs:
  125.       return 262 % n;
  126.     }
  127.   }
  128. }
  129.  
  130.  
  131. PROC (s_hash, "hash", 2, 0, 0, scm_hash);
  132. #ifdef __STDC__
  133. SCM
  134. scm_hash(SCM obj, SCM n)
  135. #else
  136. SCM
  137. scm_hash(obj, n)
  138.      SCM obj;
  139.      SCM n;
  140. #endif
  141. {
  142.   ASSERT(INUMP(n) && 0 <= n, n, ARG2, s_hash);
  143.   return MAKINUM(scm_hasher(obj, INUM(n), 10));
  144. }
  145.  
  146. PROC (s_hashv, "hashv", 2, 0, 0, scm_hashv);
  147. #ifdef __STDC__
  148. SCM
  149. scm_hashv(SCM obj, SCM n)
  150. #else
  151. SCM
  152. scm_hashv(obj, n)
  153.      SCM obj;
  154.      SCM n;
  155. #endif
  156. {
  157.   ASSERT(INUMP(n) && 0 <= n, n, ARG2, s_hashv);
  158.   if ICHRP(obj) return MAKINUM((unsigned)(scm_downcase[ICHR(obj)]) % INUM(n));
  159.   if (NIMP(obj) && NUMP(obj)) return MAKINUM(scm_hasher(obj, INUM(n), 10));
  160.   else return MAKINUM(obj % INUM(n));
  161. }
  162.  
  163. PROC (s_hashq, "hashq", 2, 0, 0, scm_hashq);
  164. #ifdef __STDC__
  165. SCM
  166. scm_hashq(SCM obj, SCM n)
  167. #else
  168. SCM
  169. scm_hashq(obj, n)
  170.      SCM obj;
  171.      SCM n;
  172. #endif
  173. {
  174.   ASSERT(INUMP(n) && 0 <= n, n, ARG2, s_hashq);
  175.   return MAKINUM((((unsigned) obj) >> 1) % INUM(n));
  176. }
  177.  
  178.  
  179. #ifdef __STDC__
  180. void
  181. scm_init_hash (void)
  182. #else
  183. void
  184. scm_init_hash ()
  185. #endif
  186. {
  187. #include "hash.x"
  188. }
  189.  
  190.